package com.uyong.study.datastruct;

/**
 * 二叉查找树，插入、删除、查找O(logn)
 * 
 * @author gonggy
 * @since 2019-02-13
 */
public class BinarySearchTree {

	private Node tree;

	public BinarySearchTree(Node tree) {
		this.tree = tree;
	}

	public Node find(int data) {
		Node node = tree;
		while (node != null) {
			if (data < node.data) {
				node = node.left;
			} else if (data > node.data) {
				node = node.right;
			} else {
				return node;
			}
		}
		return null;
	}

	public void insert(int data) {
		if (tree == null) {
			tree = new Node(data);
			return;
		}
		Node node = tree;
		while (node != null) {
			if (data < node.data) {
				if (node.left == null) {
					node.left = new Node(data);
					return;
				}
				node = node.left;
			} else {
				if (node.right == null) {
					node.right = new Node(data);
					return;
				}
				node = node.right;
			}
		}
	}

	public void delete(int data) {
		Node deleted = tree; // 需要删除的节点
		Node deletedParent = null; // 需要删除节点的父节点
		// 找到需要删除的节点
		while (deleted != null && deleted.data != data) {
			deletedParent = deleted;
			if (data > deleted.data) {
				deleted = deleted.right;
			} else {
				deleted = deleted.left;
			}
		}
		if (deleted == null) {
			return;
		}

		// 要删除的节点有两个子节点
		if (deleted.left != null && deleted.right != null) {
			// 查找出右子树中的最小节点
			Node minP = deleted.right;
			Node minPP = deleted; // minPP代表minP的父节点
			while (minP.left != null) {
				minPP = minP;
				minP = minP.left;
			}
			// 将minP的数据替换到需要删除的节点中
			deleted.data = minP.data;
			// 下面就变成删除minP节点了，minP节点要不是叶节点，要不是只有右子节点
			deleted = minP;
			deletedParent = minPP;
		}

		// 要删除的节点是叶节点或者只有一个子节点
		Node deletedChild = null;
		if (deleted.left != null) {
			deletedChild = deleted.left;
		} else if (deleted.right != null) {
			deletedChild = deleted.right;
		}

		if (deletedParent == null) {
			tree = deletedChild; // 删除的是根节点
		} else if (deletedParent.left == deleted) {
			deletedParent.left = deletedChild;
		} else {
			deletedParent.right = deletedChild;
		}
	}
}
